
/* 
 *  Copyright (c) 2008 Paul Banks [http://www.paulbanks.org/contact]
 *
 *  This file is free software: you may copy, redistribute and/or modify it  
 *  under the terms of the GNU General Public License as published by the  
 *  Free Software Foundation, either version 2 of the License, or (at your  
 *  option) any later version.  
 *  
 *  This file is distributed in the hope that it will be useful, but  
 *  WITHOUT ANY WARRANTY; without even the implied warranty of  
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  
 *  General Public License for more details.  
 *  
 *  You should have received a copy of the GNU General Public License  
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.  
 *
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>

class Win;
class Board;
class Piece {

	public:
		unsigned char nValue;
		unsigned char nAttr;
		Win* win;
		unsigned char nStore;
		unsigned char nRotate;

		void SetFromValue(int v) {
			win = NULL;
			nAttr = v >> 4;
			nValue = v & 0x0F;
			nStore = v;
			nRotate = 0;
		}

		void ZeroIfWin() {
			if (win==NULL)
				return;
			SetFromValue(0);
		}

};

class Point {
	public:
		int x;
		int y;
		void SetPoint(int _x, int _y) { x = _x; y = _y; }
};

class Triple {
	public:
		Point p[3];
		Point& operator[](int v) {
			return p[v];
		}
};

class Play;
typedef std::vector<Play> Plays;
class Play {
	public:
		Triple t;
		int Direction;
		void Set(Triple& _t, int r) {
			t = _t;
			Direction = r;
		}

		void Print() {
			for (int i=0;i<3;i++)
				printf("(%d, %d) ", t.p[i].x, t.p[i].y);
			printf("d=%d\n", Direction);
		}
};


class Win {

	public:
		unsigned char nBlocks;
		unsigned char nStars;
		unsigned char isProcessed;

		Win() {
			nBlocks = 0;
			nStars = 0;
			isProcessed = 0;
		}

		void Add(Piece& p) {
			if (p.win)
				return;
			p.win = this;
			nBlocks++;
		}

		int Score() {
			return nBlocks * (1 + nStars);
		}

};

class ITripleAction {
	public:
		virtual void Do(Board& b, Triple& pieces) = 0;
};

class Board {

	public:
		Plays plays;
		std::vector<Win*> winners;
		Piece pieces[90];

		int Score;
		int Generation;

		Board() {
			Score = 0;
			Generation = 0;
		}

		Board(const char* szFilename) {
			Generation = 0;
			Score = 0;
			FILE* fBoard = fopen(szFilename, "r");
			if (!fBoard)
				throw 1;
			for (int i=0;i<90;i++) {
				int v;
				fscanf(fBoard, "%02X", &v);
				pieces[i].SetFromValue(v);
			}
		}

		Piece* p(int x, int y) {
			return pieces + (10*y)+x;
		}

		Piece* p(Point p) {
			return pieces + (10*p.y)+p.x;
		}

		void Print() {

			printf("G=%d", Generation);
			for (int y=0;y<9;y++) {
				printf("\n");
				for (int x=0;x<10;x++) {
					Piece* p = this->p(x,y);
					if (p->win)
						printf("W  ");
					else if (p->nRotate)
						printf("rr ");
					else if (p->nValue==0)
						printf("   ");
					else
						printf("%02X ", p->nStore);
				   	
				}
			}

			printf("\n\n");
		}

		void RunTriples(ITripleAction* action) {

			Triple t;

			for (int x=0;x<10;x++) {

				// Down then across for even columns
				if (x%2==0) {
					for (int y=0;y<7;y++) {
						t.p[0].SetPoint(x,y);
						t.p[1].SetPoint(x,y+1);
						
						if (x<9) {
							t.p[2].SetPoint(x+1, y+1);
							action->Do(*this, t);
						}

						if (x>0) {
							t.p[2].SetPoint(x-1, y+1);
							action->Do(*this, t);
						}
					}

				}

				// Up then across for odd columns
				else {
					for (int y=8;y>0;y--) {
						t.p[0].SetPoint(x,y);
						t.p[1].SetPoint(x, y-1);
						
						if (x<9) {
							t.p[2].SetPoint(x+1, y-1);
							action->Do(*this, t);
						}

						if (x>0) {
							t.p[2].SetPoint(x-1, y-1);
							action->Do(*this, t);
						}

					}

				}

			}

		}

		class MarkWinners : public ITripleAction {
			public:
				virtual void Do(Board& b, Triple& t) {

					// Get pieces
					Piece* pieces[3];
					for (int i=0;i<3;i++) {
						pieces[i] = b.p(t[i]);
						if (pieces[i]->nValue==0)
							return;
					}

					// First, validate triple is a winner
					if (	pieces[0]->nValue != pieces[1]->nValue || 
							pieces[0]->nValue != pieces[2]->nValue
					   )
						return;

					// Get win object.
					Win* w = NULL;
					for (int p=0;p<3;p++) {
						if (pieces[p]->win) {
							w = pieces[p]->win;
							break;
						}
					}
					if (!w) {
						w = new Win();
						b.winners.push_back(w);
					}

					// Process pieces
					for (int p=0;p<3;p++)
						w->Add(*pieces[p]);
				
				}

		};

		void CleanUpColumn(int x) {
				int w = 8;
				for (int y=8;y>=0;y--) {
					Piece& pp = *p(x,y);
					if (pp.nValue>0) {
						*p(x,w) = pp;
						w--;
					}
				}
				for (int y=w;y>=0;y--)
					p(x,y)->nValue = 0;
		}

		int RunBoard() {

			int score, runningscore = 0;
			do {

				// Mark all winners
				RunTriples(new MarkWinners());

				// Set winners to empty
				for (int x=0;x<10;x++)
			   		for (int y=0;y<9;y++) {
				   		p(x,y)->ZeroIfWin();
						p(x,y)->nRotate = 0;
					}
				
				// Clear up empty space
				for (int x=0;x<10;x++)
					CleanUpColumn(x);

				// Add up score + delete winners objects;
				score = 0;
				for (int i=0;i<winners.size();i++) {
					score = winners[i]->Score();
					runningscore += score;
					delete winners[i];
				}
				winners.clear();

			} while (score>0);

			return runningscore;

		}

		void Rotate(Play& p) {
			Rotate(p.t, p.Direction);
		}

		void Rotate(Triple& t, int n) {

			for (int i=0;i<n;i++) {
				Piece tmp = *p(t[0]);
				*p(t[0]) = *p(t[1]);
				*p(t[1]) = *p(t[2]);
				*p(t[2]) = tmp;
			}

			for (int i=0;i<3;i++)
				p(t[i])->nRotate = n;
		}



		class PlayTriples : public ITripleAction {
			public:

				PlayTriples(int _MaxDepth) {
					MaxDepth = _MaxDepth;
					plays = new Play[MaxDepth+1];
					BestScore = 0;
					BestDepth = 0;
				}

				~PlayTriples() {
					delete [] plays;
				}
				
				int MaxDepth;
				int BestScore, BestDepth;
				Play* plays;

				virtual void Do(Board& b, Triple& t) {
					
					// Can't use empty pieces
					for (int i=0;i<3;i++) 
						if (b.p(t[i])->nValue==0)
							return;

					// Play both rotations
					int score;
					Board bPlay;
					int currentbest = BestScore;
					for (int r=1;r<=2;r++) {
						bPlay = b; // Initialise board to current generation
						bPlay.Rotate(t, r);
						score = bPlay.RunBoard();
						bPlay.Score += score;
						if (score) {
							//printf("Score=%d Generation=%d TreeScore=%d Best=%d@%d\n", 
									//score, b.Generation, bPlay.Score, BestScore, BestDepth);

							if (++bPlay.Generation <= MaxDepth)
								bPlay.RunTriples(this);

							if (bPlay.Score > BestScore) {
								if (bPlay.Generation >= MaxDepth)
									BestDepth = b.Generation + 1;
								BestScore = bPlay.Score;
							}

							if (BestScore > currentbest) {
								currentbest = BestScore;
								plays[b.Generation].Set(t, r);
								if (b.Generation==0)
									printf("Best so far %d\n", BestScore);
							}

						}
					}

				}	

		};

		void FindPlays(int nMaxDepth = 2) {
			PlayTriples* playtriples = new PlayTriples(nMaxDepth);
			RunTriples(playtriples);
		
			plays.clear();
			for (int i=0;i<playtriples->BestDepth;i++)
				plays.push_back(playtriples->plays[i]);

			delete playtriples;
		};

		int PlayGetCount() {
			return plays.size();
		}
		Play& PlayGet(int i) {
			return plays[i];

		}


};


